package cn.edu.anan.datastructure.line;

/**
 * 单链表实现思路：
 *     1.空闲一个头节点，即头节点不存储数据
 *     2.这样有利于简化链表的实现
 */
public class SingleLinkedList<E> {

    // 链表大小
    private int size;

    public int getSize() {
        return size;
    }

    // 链表头节点
    private Node<E> head;
    // 链表尾节点
    private Node<E> tail;

    public SingleLinkedList(){
        head = new Node<E>();
        tail = head;

        size = 1;
    }

    /**
     * 在链表结尾插入元素
     */
    public boolean add(E e){
        // 创建节点
        Node<E> node = new Node<E>();
        node.setE(e);

        tail.next = node;
        tail = node;

        size ++;
        return true;
    }

    /**
     * 在指定索引位置，插入节点
     */
    public boolean insertPos(int pos,E e){

       // 判断索引位置有效性
        if(pos < 1 || pos > size ){
            return  false;
        }

        // 创建节点
        Node<E> node = new Node<E>();
        node.setE(e);

        // 获取插入位置节点
        Node<E> posNode = get(pos - 1);
        node.next = posNode.next;
        posNode.next = node;

        size ++;
        return true;
    }

    /**
     * 删除链表尾元素
     */
    public boolean remove(){

        // 获取链表倒数第二个元素
        Node<E> node = get(getSize() - 2);
        tail = node;
        node.next = null;

        size -- ;
        return true;
    }

    /**
     * 删除指定位置的元素（不能删除头节点）
     */
    public boolean delPos(int pos){

        // 判断索引位置有效性
        if(pos < 1 || pos > size){
            return false;
        }

        // 如果删除的是最后一个元素
        if((pos + 1) == size){
            remove();
        }else{
            // 获取删除元素节点
            Node<E> node = get(pos);
            // 获取删除元素的前一个节点
            Node<E> preNode = get(pos - 1);

            // 删除操作
            preNode.next = node.next;

            size --;
        }

        return true;
    }


    /**
     * 获取指点索引的链表节点
     */
    public Node<E> get(int index){
        // 判断索引有效性
        if(index < 0 || index > size - 1){
            return null;
        }

        Node<E> node = head;
        for(int i=0; i< index; i++){
            node = node.next;
        }

        return node;
    }

    /**
     * 获取指定索引位置的数据
     */
    public E getValue(int index){
        // 获取节点
        Node<E> node = get(index);
        if(node == null){
            return  null;
        }

        return  node.e;
    }

    /**
     * 链表节点：Node<E>
     */
    class Node<E>{
        private E e;
        private Node<E> next;

        public E getE() {
            return e;
        }

        public void setE(E e) {
            this.e = e;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }
}
